/*
 * @lc app=leetcode.cn id=60 lang=typescript
 *
 * [60] 排列序列
 */

// @lc code=start
function getPermutation(n: number, k: number): string {
  // [1,n-1]的阶乘
  let base = 1;
  for (let i = 1; i < n; i++) {
    base *= i;
  }
  // 标识某个数字是否被使用过
  const mark = new Array(n + 1).fill(0);
  // 选择第n个未被使用的数字
  const pick = (n: number): number => {
    let i = 0;
    let cnt = 0;
    while (cnt < n) {
      i += 1;
      cnt += mark[i] === 0 ? 1 : 0;
    }
    mark[i] = 1;
    return i;
  };

  let ans = '';
  for (let i = n; i >= 1; i--) {
    // 首位数字
    const index = 1 + Math.floor((k - 1) / base);
    ans += pick(index).toString();
    // 缩小范围
    k -= (index - 1) * base;
    base /= i - 1;
  }

  return ans;
}
// @lc code=end
